package com.tim.test.leetcode.exam;


import java.util.HashSet;
import java.util.Set;

public class HuaWei20230621 {

    /*
     给定一个二维网格和一个单词，找出该单词是否存在于网格中。
    单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
    示例:
    board =
    [
      ['A','B','C','E'],
      ['S','F','C','S'],
      ['A','D','E','E']
    ]
    给定 word = "ABCCED", 返回 true
    给定 word = "SEE", 返回 true
    给定 word = "ABCB", 返回 false

    dfs；相邻：上下左右
    Set标记已使用；是单词前缀时加入Set，每个dfs Set独立
     */
    static char[][] board = new char[][]{
            {'A','B','C','E'},
            {'S','F','C','S'},
            {'A','D','E','E'}
    };
    static String word = "ABFCSEEDF";
    public static void main(String[] args) {
        boolean flag = false;// true时跳出
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                flag = dfs("", 0, 0, new HashSet<>());
                if(flag){
                    System.out.println(true);
                    return;
                }
            }
        }
        System.out.println(false);
    }

    /**
     * word；目标字符串
     * board；目标数组
     * usedSet；已使用位置
     * pre；前序字符串
     *
     * 或操作
     */
    public static boolean dfs(String pre, int i, int j, Set<String> usedSet){
        // 越界、已使用
        if(i<0 || i>=board.length){
            return false;
        }
        if(j<0 || j>=board[0].length){
            return false;
        }
        if(usedSet.contains(i+","+j)){
            return false;
        }
        char aChar = board[i][j];
        if(!word.startsWith(pre+aChar)){
            // 非前缀，返回
            return false;
        }
        usedSet.add(i+","+j);
        if(word.equals(pre+ aChar)){
            return true;
        }
        pre += aChar;
        // 上下左右
        return dfs(pre, i-1, j, new HashSet<>(usedSet))
                || dfs(pre, i+1, j, new HashSet<>(usedSet))
                || dfs(pre, i, j-1, new HashSet<>(usedSet))
                || dfs(pre, i, j+1, new HashSet<>(usedSet));
    }
}
